package midalgorithms.math;

import java.util.HashMap;

public class _07FractionToDecimal {
    public static String fractionToDecimal(int numerator, int denominator) {
        /**
         * 该方案无法计算数据是 Integer.MIN_VALUE 的情况
         */
        if (numerator == 0){
            return "0";
        }
        boolean _if = (numerator > 0 && denominator > 0) || (numerator < 0 && denominator < 0);
        numerator = Math.abs(numerator);
        denominator = Math.abs(denominator);
        //  如果分子比分母大，且可整除时，直接return
        if (numerator >= denominator && numerator % denominator == 0){
            return _if ? String.valueOf(numerator / denominator) : "-" + numerator / denominator;
        }else if (numerator >= denominator && numerator % denominator != 0){
            //  整数部分
            String pre = String.valueOf(numerator / denominator);
            String next = toDecimal(numerator % denominator,denominator);
            return _if ? pre +"."+ next : "-" + pre +"."+ next;
        }
        return _if ? "0." + toDecimal(numerator,denominator) : "-" + "0." + toDecimal(numerator,denominator);
    }

    private static String toDecimal(int numerator, int denominator) {
        //  此时的分子已经比分母小了
        //  判断有限小数和无限循环小数
        boolean ifLimited = false;
        int n = denominator;
        while (true){
            if (n % 2 == 0){
                n /= 2;
                continue;
            }
            if (n % 5 == 0){
                n /= 5;
                continue;
            }
            if (n == 1){
                ifLimited = true;
                break;
            }else {
                break;
            }
        }
        if (ifLimited){
            //  有限小数
            String res = String.valueOf((double)numerator / (double)denominator);
            return res.substring(2);
        }
        //  无限循环小数
        //  问题的难点是找出循环的最小周期
        //  方法：每次将被除数乘10，做除法运算后得到的余数如果等于之前某个被除数时，则当前位置重复循环
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int index = 0;
        hashMap.put(numerator,index++);
        StringBuilder res = new StringBuilder();
        res.append(10 * numerator / denominator);
        int t;
        while (true){
            numerator *= 10;
            if (hashMap.containsKey(numerator % denominator)){
                t = index - hashMap.get(numerator % denominator);
                break;
            }
            numerator = numerator % denominator;
            res.append(10*numerator / denominator);
            hashMap.put(numerator,index++);
        }
        res.insert(res.length() - t,"(");
        res.append(")");
        return res.toString();
    }
}
